package cn.yuemouren.hash;

import java.util.TreeMap;

/**
 * @Author: Timi
 * @Description: 实现hash表
 * @Date: 2020/7/18 19:14
 * @Version: v1.0
 */
public class HashTable<K,V> {

    private final int[] capacity = {53,97,193,389,769,1543,3879,6151,12289,24593,
                                    49157,98317,196613,393241,786433,1572869,3145739,
                                    6291469,12582917,25165843,50331653,100553319,
                                    201326611,402653189,805306458};

    private final static int UPPER_TOL = 10;
    private final static int LOWER_TOL = 2;

    private TreeMap<K,V>[] data;
    private int size;
    private int capacityIndex = 0;
    private int M;

    public HashTable() {
        this.data = new TreeMap[9];
        size = 0;
        this.M = capacity[capacityIndex];
        for (int i = 0; i < data.length; i++)
            data[i] = new TreeMap<K,V>();
    }

    /**
     * 根据k获取hash值
     * @param k
     * @return
     */
    private int hash(K k){
        return (k.hashCode() & 0x7fffffff) % M;
    }

    /**
     * 添加数据
     * @param key
     * @param value
     */
    public void add(K key,V value){
        TreeMap<K,V> map = data[hash(key)];
        if(map.containsKey(key)){
            map.put(key,value);
        } else{
            map.put(key,value);
        }
        if(size >=  UPPER_TOL * M && capacityIndex < capacity.length){
            resize(capacity[++capacityIndex]);
        }
    }

    /**
     * 动态改变数组的大小
     * @param capacity
     */
    private void resize(int capacity) {
        TreeMap<K,V>[] treeMaps = new TreeMap[capacity];
        for(int i = 0; i < treeMaps.length; i++)
            treeMaps[i] = new TreeMap<K,V>();
        int oldM = M;
        this.M = capacity;
        for (int i = 0; i < oldM; i++){
            TreeMap<K, V> map = data[i];
            map.forEach( (key,value) -> {
                treeMaps[hash(key)].put(key,value);
            });
        }
    }

    /**
     * 修改数据
     * @param key
     * @param value
     * @return
     */
    public V set(K key,V value){
        TreeMap<K, V> map = data[hash(key)];
        if(!map.containsKey(key))
            throw new RuntimeException("data is not have!");
        V result = map.get(key);
        map.put(key,value);
        return result;
    }

    /**
     * 删除
     * @param key
     * @return
     */
    public V remove(K key){
        TreeMap<K, V> map = data[hash(key)];
        V result = null;
        if(map.containsKey(key)){
            result =  map.remove(key);
            size--;
        }
        if(size <= LOWER_TOL * M && capacityIndex >= 0){
            resize(capacity[--capacityIndex]);
        }
        return result;
    }

    /**
     * 获取数据
     * @param key
     * @return
     */
    public V get(K key){
        return data[hash(key)].get(key);
    }

    /**
     * 是否包含
     * @param key
     * @return
     */
    public boolean contains(K key){
        return data[hash(key)].containsKey(key);
    }
}
